#include <iostream>
#include <vector>
#include <stack>
using namespace std;

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int n = nums.size();
        int left = 0;
        int right = n - 1;
        int x = nums[right];
        while (left < right)
        {
            int mid = (left + right) / 2;
            if (nums[mid] == target)
            {
                return true;
            }
            if (nums[mid] < x)
            {
                right = mid;
            }
            else
            {
                left = mid + 1;
            }
        }
        int end = left - 1;
        int begin = left;
        left = 0;
        right = n - 1;
        while (left <= end)
        {
            int mid = (left + end) / 2;
            if (nums[mid] > target)
            {
                end = mid - 1;
            }
            else if (nums[mid] < target)
            {
                left = mid + 1;
            }
            else
            {
                return true;
            }
        }
        while (begin <= right)
        {
            int mid = (begin + right) / 2;
            if (nums[mid] > target)
            {
                right = mid - 1;
            }
            else if (nums[mid] < target)
            {
                begin = mid + 1;
            }
            else
            {
                return true;
            }
        }
        return false;
    }
};

class Solution {
public:
    void push(int n, string s, stack<string> st)
    {
        if (n == 0 && st.empty())
        {
            ret.push_back(s);
            return;
        }
        if (n > 0 && st.empty())
        {
            string s1 = s;
            stack<string> st1 = st;
            st1.push("(");
            push(n - 1, s1 += '(', st1);
            return;
        }
        if (n > 0 && !st.empty())
        {
            string s1 = s;
            stack<string> st1 = st;
            st1.push("(");
            push(n - 1, s1 += '(', st1);
        }
        if (n == 0 && !st.empty())
        {
            string s1 = s;
            stack<string> st1 = st;
            st1.pop();
            push(n, s1 += ')', st1);
        }
        if (n > 0 && !st.empty())
        {
            string s1 = s;
            stack<string> st1 = st;
            st1.pop();
            push(n, s1 += ')', st1);
        }
    }
    vector<string> generateParenthesis(int n) {
        stack<string> st;
        string s;
        push(n, s, st);
        return ret;
    }
    vector<string> ret;
};